#include <cstdio>
#include <cstring>
#include <stdlib.h>
const int TABLE_SIZE = 499883; // = 124970 * 4 + 3
const int public_area_begin=350000;
// const int TABLE_SIZE = 23;
// const int public_area_begin = 15;
struct hash_entry
{
    char *my_string;
    int my_data;
    hash_entry()
    {
        my_string = NULL;
        my_data = 0;
    }
    hash_entry(char *str, int data) : my_data(data)
    {
        my_string = new char[strlen(str) + 1];
        strcpy(my_string, str);
    }
};
struct hashing_strategy
{
    virtual int operator()(char *str, int N) = 0;
};
struct naive_hashing : public hashing_strategy
{
    int operator()(char *str, int N) override;
};
struct collision_strategy
{
    virtual void init() = 0; // pure virtual function
    virtual int operator()(hash_entry *Table, int table_size, int last_choice) = 0;
};
struct linear_probe : public collision_strategy
{
    void init();
    int operator()(hash_entry *Table, int table_size, int last_choice) override;
};
struct hashtable
{
    hash_entry *Table;
    int table_size;
    hashing_strategy *my_hashing; // 如果改为hashing_strategy my_hashing, 即不是用指针作为hashtable的成员, 而是让hashing_strategy结构体直接作为hashtable的成员. 会发生什么bug?
    collision_strategy *my_collision;
    hashtable(int size, hashing_strategy *hashing, collision_strategy *collision)
        : table_size(size), my_hashing(hashing), my_collision(collision)
    {
        Table = new hash_entry[table_size];
    }
    bool insert(hash_entry entry, bool pubOrNot)
    {
        if (pubOrNot)
        {
            int last_choice = (*my_hashing)(entry.my_string, public_area_begin);
            my_collision->init();
            while (Table[last_choice].my_string != NULL)
            { // loop infinitely? return false when no more space?
                last_choice = (*my_collision)(Table, table_size, last_choice);
            }
            Table[last_choice] = entry;
            return true;
        }
        else
        {
            int last_choice = (*my_hashing)(entry.my_string, table_size);
            my_collision->init();
            while (Table[last_choice].my_string != NULL)
            { // loop infinitely? return false when no more space?
                last_choice = (*my_collision)(Table, table_size, last_choice);
            }
            Table[last_choice] = entry;
            return true;
        }
    }
    int query(char *query_string, bool pubOrNot)
    {
        if (pubOrNot)
        {
            int last_choice = (*my_hashing)(query_string, public_area_begin);
            my_collision->init();
            while (Table[last_choice].my_string != NULL &&
                   strcmp(Table[last_choice].my_string, query_string) != 0)
            { // 未处理的情况: 哈希表已满?
                last_choice = (*my_collision)(Table, table_size, last_choice);
            }
            if (Table[last_choice].my_string == NULL)
            {
                return -1;
            }
            else
            {
                return Table[last_choice].my_data;
            }
        }
        else
        {
            int last_choice = (*my_hashing)(query_string, table_size);
            my_collision->init();
            while (Table[last_choice].my_string != NULL &&
                   strcmp(Table[last_choice].my_string, query_string) != 0)
            { // 未处理的情况: 哈希表已满?
                last_choice = (*my_collision)(Table, table_size, last_choice);
            }
            if (Table[last_choice].my_string == NULL)
            {
                return -1;
            }
            else
            {
                return Table[last_choice].my_data;
            }
        }
    }
};

//*****************************************************************
//*****************************************************************
//Below is my Code

struct ascii_hashing_strategy : public hashing_strategy
{
    int operator()(char *str, int table_size) //字符串、表长
    {
        unsigned int seed = 131;
        unsigned int hash = 0;
        while (*str)
        {
            hash = hash * seed + (*str++);
        }
        return (int)(hash & 0x7fffffff) % table_size;
    }
};

struct utf8_hashing_strategy : public hashing_strategy
{
    int operator()(char *str, int table_size) //字符串、表长
    {
        unsigned int seed = 131;
        unsigned int hash = 0;
        while (*str)
        {
            unsigned char a = *str++;
            // char bin[100];
            // itoa(a, bin, 2);
            // FILE* fwt=fopen("testL.out","a");
            // fprintf(fwt,"%s\n", bin);
            if (a >> 7 == 1)
            {
                if ((a >> 5) % 2 == 0) //2字符
                {
                    a += *str++;
                    //printf("     2字符");
                }
                else //3字符
                {
                    a += *str++;
                    a += *str++;
                    //printf("     3字符");
                }
            }
            else //1字符
            {
                ;
            }
            hash = hash * seed + a;
        }
        return (int)(hash & 0x7fffffff) % table_size;
    }
};

struct quaduatic_probing_collision_strategy : public collision_strategy
{
    int i = -1;
    char direction = 'r';
    int lastRight = 0;
    int lastLeft = 0;
    void init(void)
    {
        i = 1;
        direction = 'r';
        lastLeft = 0;
        lastRight = 0;
    }
    int operator()(hash_entry *Table, int table_size, int last_choice)
    {
        if (i == -1)
        {
            lastRight = last_choice;
            lastLeft = last_choice;
        }
        if (direction == 'r')
        {
            i += 2;
            lastRight = (lastRight + i) % table_size;
            direction = 'l';
            return lastRight;
        }
        else
        {
            lastLeft = (lastLeft + i) % table_size;
            if (lastLeft < 0)
            {
                lastLeft += table_size;
            }
            direction = 'r';
            return lastLeft;
        }
    }
};

struct public_overflow_collision_strategy : public collision_strategy
{
    int public_index = 0;

    void init(void)
    {
        public_index = 0;
        return;
    }
    int operator()(hash_entry *Table, int table_size, int last_choice)
    {
        public_index++;
        return public_area_begin + public_index;
    }
};